#include <iostream>
#include <vector>
#include <stack>
#include <utility>
#include <algorithm>
#include <sys/time.h>

using namespace std;

//给定坐标x,y在board中找到所有值等于ch的邻居
stack< std::pair<int,int> > findNeighbors(vector< vector<char> >& _board,int x,int y,char ch,vector< pair<int,int> >& visited )
{
  vector< vector<char> > board(_board.begin(),_board.end());
  {
    int m = board.size();
    int n = board.at(0).size();
    board.insert(board.begin(), vector<char> (n,0)  );
    board.push_back(vector<char> (n,0));

  }

  int m = board.size();
  int n = board.at(0).size();
  x++;
  stack< pair<int,int> > ret;
  if(0==y)
  {
    if(board[x-1][0] == ch)
    {
      if( std::find(visited.begin(), visited.end(), pair<int,int>(x-1-1,0) ) == visited.end() )
        ret.push( pair<int,int>(x-1-1,0) );
    }
    if(board[x+1][0] == ch)
    {
      if( std::find(visited.begin(), visited.end(), pair<int,int>(x+1-1,0) ) == visited.end() )
        ret.push( pair<int,int>(x+1-1,0) );
    }
    if(board[x][1] == ch)
    {
      if( std::find(visited.begin(), visited.end(), pair<int,int>(x-1,1) ) == visited.end() )
        ret.push( pair<int,int>(x-1,1) );
    }
  }
  else if( n-1==y )
  {
    if(board[x-1][n-1] == ch)
    {
      if( std::find(visited.begin(), visited.end(), pair<int,int>(x-1-1,n-1) ) == visited.end() )
        ret.push( pair<int,int>(x-1-1,n-1) );
    }
    if(board[x+1][n-1] == ch)
    {
      if( std::find(visited.begin(), visited.end(), pair<int,int>(x+1-1,n-1) ) == visited.end() )

        ret.push( pair<int,int>(x+1-1,n-1) );
    }
    if(board[x][n-2] == ch)
    {
      if( std::find(visited.begin(), visited.end(), pair<int,int>(x-1,n-2) ) == visited.end() )
        ret.push( pair<int,int>(x-1,n-2) );
    }
  }
  else
  {
    if(board[x][y-1] == ch)
    {
      if( std::find(visited.begin(), visited.end(), pair<int,int>(x-1,y-1) ) == visited.end() )
        ret.push( pair<int,int>(x-1,y-1) );
    }

    if(board[x][y+1] == ch)
    {
      if( std::find(visited.begin(), visited.end(), pair<int,int>(x-1,y+1) ) == visited.end() )
        ret.push( pair<int,int>(x-1,y+1) );
    }

    if(board[x+1][y] == ch)
    {
      if( std::find(visited.begin(), visited.end(), pair<int,int>(x+1-1,y) ) == visited.end() )
        ret.push( pair<int,int>(x+1-1,y) );
    }

    if(board[x-1][y] == ch)
    {
      if( std::find(visited.begin(), visited.end(), pair<int,int>(x-1-1,y) ) == visited.end() )
        ret.push( pair<int,int>(x-1-1,y) );
    }
  }


  return ret;


}




bool existIter(vector< vector<char> > &board,int i, int j,string word,int k,vector< pair<int,int> >& visited )
{
  if( (k+1) > word.size() )
  {
    return true;
  }

  char ch  =  word.at(k);
  visited.push_back( pair<int,int>(i,j) );
  stack< pair<int,int> >  nb = findNeighbors(board,i,j,ch,visited );
  if( nb.size() > 0 )
  {
    if( (k+1) == word.size() )
    {
      return true;
    }
    else
    {
      for(int i=0;i<nb.size();++i )
      {
        pair<int,int> p = nb.top();
        nb.pop();
        existIter(board,p.first,p.second,word, ++k,visited );
      }
    }

  }
  else
  {
    return false;
  }

}

bool exist(vector< vector<char> >& board, string word)
{
  bool ret = false;
  if( board.size() <1 )
    return ret;

  for( int i=0; i < board.size() ; ++i)
  {
    for(int j=0; j < board.at(0).size(); ++j)
    {

      if( board[i][j] == word[0] )
      {
        //find if word[1] exist in iterj's neighbors
        int k=1;
        vector< pair<int,int> > visited ;
        ret = existIter(board,i,j,word,k,visited);
        if( ret )
        {
          return ret;
        }

      }

    }
  }


  return ret;

}






int main(int argc,char *argv[])
{
  vector< vector<char> > board;
  vector<char> a;
 /* a.push_back('c');*/
  a.push_back('a');
  a.push_back('b');

  board.push_back(a);

  vector<char> b;
  b.push_back('c');
  b.push_back('d');
  //b.push_back('a');
  board.push_back(b);

/*  vector<char> c;*/
  //c.push_back('b');
  //c.push_back('c');
  //c.push_back('d');
  /*board.push_back(c);*/

  struct  timeval    tv1,tv2;
  struct  timezone   tz;
  int time1 = gettimeofday(&tv1,&tz);

  //func();
  string s("cdb");
  bool ret = exist(board,s);

  int time2 = gettimeofday(&tv2,&tz);
  cout << "time consuming(local machine/leetcode server):"<<endl
    <<"leetcode server time consuming should be less than 500ms"<<endl
    << tv2.tv_usec - tv1.tv_usec <<"us/"<<0.11*( tv2.tv_usec - tv1.tv_usec )<<"ms"<< endl;

  cout <<"ret:"<<ret<<endl;



  return 0;
}
